#pragma once

#include "controls.h"

namespace outline {

template <class R>
struct controls<R>::node {
	uint pl, pr; // pieces to the left and to the right; they may differ only if the node joins two pieces
	R tl, tr; // times on the left and the right pieces
	point<R> p, cl, cr;
};

template <class R>
template <class F>
void controls<R>::sample(F const & f, R max_distance, bool include_last_point, bool subdiv_min_twice) const
{
	uint p = pieces();
	assert (p > 0);
	std::vector<node> vec(p + 1); //this vector stores bezier nodes in reverse direction
	{
		node & n0 = vec[p];
		n0.pr = 0;
		n0.tr = 0;
		n0.p =  (*this)[0];
		n0.cr = (*this)[1];
	}
  uint i;
	for (i = 1; i < p; ++i) {
		node & ni = vec[p-i];
		ni.pl = i-1;
		ni.pr = i;
		ni.tl = 1;
		ni.tr = 0;
		ni.cl = (*this)[3*i-1];
		ni.p =  (*this)[3*i];
		ni.cr = (*this)[3*i+1];
	}
	{
		node & np = vec[0];
		np.pl = i-1;
		np.tl = 1;
		np.cl = (*this)[3*p-1];
		np.p =  (*this)[3*p];
	}

	R hsq = 1 / R(3) * square(max_distance);
	while (vec.size() > 1) {
		node const & n0 = vec[vec.size() - 1];
		node const & n1 = vec[vec.size() - 2];
		assert (n0.pr == n1.pl);
		assert (n0.tr < n1.tl);

		//3 * (square(n0.cr - n0.p) + square(n1.cl - n0.cr) + square(n1.p - n1.cl)) is the top limit for the bezier between n0 & n1 length
		if (square(n0.cr - n0.p) + square(n1.cl - n0.cr) + square(n1.p - n1.cl) < hsq
			&& !(subdiv_min_twice && (n0.tr == 0 && n1.tl >= R(0.5) || n0.tr <= R(0.5) && n1.tl == 1))) //Bezier piece was not divided twice yet
		{
			f(n0.pr, n0.tr, n0.p, n0.cr - n0.p);
			vec.pop_back();
			continue;
		}

		point<R> a = R(0.5) * (n0.p + n0.cr);
		point<R> b = R(0.5) * (n0.cr + n1.cl);
		point<R> c = R(0.5) * (n1.cl + n1.p);
		point<R> d = R(0.5) * (a + b);
		point<R> f = R(0.5) * (b + c);
		point<R> e = R(0.5) * (d + f);

		vec.push_back(n0);
		{
			node & n0 = vec[vec.size() - 1];
			node & n1 = vec[vec.size() - 2];
			node & n2 = vec[vec.size() - 3];
			n0.cr = a;
			n1.pl = n1.pr = n0.pr;
			n1.tl = n1.tr = R(0.5) * (n0.tr + n2.tl);
			n1.cl = d;
			n1.p = e;
			n1.cr = f;
			n2.cl = c;
		}
	}

	assert (vec.size() == 1);
	if (include_last_point) {
		node const & n0 = vec[0];
		f(n0.pl, n0.tl, n0.p, n0.p - n0.cl);
	}
}

template <class R>
class controls<R>::append_pos {
	std::vector< point<R> > & samples;
public:
	append_pos(std::vector< point<R> > & s) : samples(s) { }
	void operator () (uint, R, point<R> const & pos, point<R> const &) const
		{ samples.push_back(pos); }
};

template <class R>
inline void controls<R>::sample_points(std::vector< point<R> > & samples, R max_distance, bool include_last_point, bool subdiv_min_twice) const
{
	sample(append_pos(samples), max_distance, include_last_point, subdiv_min_twice);
}

} //namespace outline
